package main.java.indi.zyj.hot100;

import main.java.indi.zyj.hot100.base.TreeNode;



public class _01_maxPathSum {

    int maxSum;

    public int maxPathSum(TreeNode root) {
        return reCur(root);
    }

    public int reCur(TreeNode node){
        if (node == null){
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        int leftMax = Math.max(reCur(node.left), 0);
        int rightMax = Math.max(reCur(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftMax + rightMax;

        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return  node.val + Math.max(leftMax, rightMax);

    }

}
